package formal.tree.ergodic;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author DengYuan2
 * @create 2021-01-20 22:34
 */
public class M_94 {
    public static void main(String[] args) {
//        Integer[] a = {1, null, 2, 3, null};
//        Integer[] a = {1, 2, 3, 4, 5, 6, 7};
        Integer[] a = {1, 2, 3};
        TreeNode treeNode = TreeNode.generateTree(a);
        List<Integer> resList = inorderTraversal2(treeNode);
        for (int i = 0; i < resList.size(); i++) {
            System.out.print(resList.get(i) + "  ");
        }
    }

    /**
     * 不会-官方解法
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> resList = new ArrayList<>();
        if (root == null) {
            return resList;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                resList.add(cur.val);
                cur = cur.right;
            }
        }
        return resList;
    }

    /**
     * 大神-类似上面的思路，写法有所不同
     * 感觉更好理解
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal3(TreeNode root) {
        ArrayList<Integer> resList = new ArrayList<>();
        if (root == null) {
            return resList;
        }
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode pop = stack.pop();
            resList.add(pop.val);
            cur=pop.right;
        }
        return resList;
    }

    /**
     * 通用的迭代方法
     * https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/bang-ni-dui-er-cha-shu-bu-zai-mi-mang-che-di-chi-t/
     * 这是中序遍历
     * 将左中右替换即可得到前序遍历、后序遍历
     *
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal2(TreeNode root) {
        ArrayList<Integer> resList = new ArrayList<>();
        if (root == null) {
            return resList;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop != null) {
                //右
                if (pop.right != null) {
                    stack.push(pop.right);
                }
                //中
                stack.push(pop);
                stack.push(null);
                //左
                if (pop.left != null) {
                    stack.push(pop.left);
                }
            } else {
                //已经在62行清理掉了null节点
//                stack.pop();
                //加入当前节点的值
                resList.add(stack.pop().val);
            }
        }
        return resList;
    }
}
